package 我的Java学习_算法基础.day_03;

import java.util.Arrays;
import java.util.Scanner;

public class _056_小顶堆与topK的具体代码实现 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        k = scanner.nextInt();
        heap = new int[k];
        int x = scanner.nextInt();
        while (x != -1) {
            deal(x);
            x = scanner.nextInt();
        }
        printResult();
    }

    static int[] heap;
    static int index = 0;
    static int k;

    /**
     * 如果数据小于等于k,直接加入堆中
     * 数据的数量等于K时，进行堆化
     *
     * @param x
     */
    private static void deal(int x) {
        if (index < k) {
            heap[index++] = x;
            if (index == k) {
                makeMinHeap(heap);

            }
        }
        //x与堆顶比较，若果x比堆顶大，x取代堆顶并向下调整
        else if (heap[0] < x) {
            heap[0] = x;
            minHeapFixDown(heap, 0, k);
            printResult();
        }

    }

    private static void printResult() {
        System.out.println(Arrays.toString(heap));
    }

    static void makeMinHeap(int[] array) {
        int n = array.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            minHeapFixDown(array, i, n);
        }
    }

    static void minHeapFixDown(int[] array, int i, int length) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left >= length) {
            return;
        }
        int min = left;
        if (right >= length) {
            min = left;
        } else if (array[right] < array[left]) {
            min = right;
        }
        if (array[i] <= array[min]) {
            return;

        }
        int temp = array[i];
        array[i] = array[min];
        array[min] = temp;
        minHeapFixDown(array, min, length);

    }
}
